package com.yeung.dynamicplan;

import java.util.HashMap;

public class 动态规划爬楼梯 {
    public static void main(String[] args) {
        int steps = 10;
        int count = getCpunt(steps, new HashMap<>());
        System.out.println(count);
    }

    /**
     * 这种递归的时间复杂度较高
     * <p>
     * 可以利用备忘录方法  优化一下
     *
     * @param map   集合map是一个备忘录。当每次需要计算F(N)的时候，
     *              会首先从map中寻找匹配元素。如果map中存在，就直接返回结果
     *              ，如果map中不存在，就计算出结果，存入备忘录中。
     * @param steps
     * @return
     */
    private static int getCpunt(int steps, HashMap<Integer, Integer> map) {
        if (steps < 1) return 0;
        if (steps == 1) return 1;
        if (steps == 2) return 2;
        if (map.containsKey(steps)) return map.get(steps);
        else {
            int count1 = getCpunt(steps - 1, map);
            int count2 = getCpunt(steps - 2, map);
            map.put(steps, count1 + count2);//存储中间结果, 以便降低消耗
            return count1 + count2;
        }


    }

    /**
     * 动态规划的实现
     * <p>
     * 性能极高
     *
     * @param steps
     * @return
     */
    private static int getStepCount(int steps) {
        if (steps == 1) return 1;
        if (steps == 2) return 2;
        int fir = 1;
        int sec = 2;
        int count = 0;
        for (int i = 3; i <= steps; i++) {
            count = fir + sec;
            fir = sec;
            sec = count;
        }
        return count;
    }
}
